/*Universidad del Valle de Guatemala
 * Algoritmos y Estructura de Datos
 * Sara López 12050
 * Matías Vasquez 12186
 * Sección: 21
 * Java Class: BinaryTree
 */

/**
 *
 * @author saralopez
 */

package javaapplication1;
import java.util.ArrayList;

public class HuffmanTree {
	
	private Elemento[] elementos;
	private ArrayList<Nodo> nodos;
	
	public HuffmanTree(String mensaje){
		elementos(mensaje);
		buildTree();
	}
	
	public void elementos(String mensaje){
		char[] caracteres = mensaje.toCharArray();
		ArrayList<Elemento> temp = new ArrayList<Elemento>();
		for(int a=0;a<caracteres.length;a++){
			int freq = 1;
			for(int b=0;b<caracteres.length;b++){
				if(caracteres[a]==caracteres[b]&& a!=b){
					freq++;
				}
			}
			String nombre = ""+caracteres[a];
			Elemento elemento;
			boolean c = true;
			for(int d=0;d<temp.size() && c; d++){
				elemento = temp.get(d);
				if(nombre.equals((String)elemento.getNombre())){
					c = false;
				}
			}	
			if(c){
				elemento = new Elemento(nombre, freq);
				temp.add(elemento);
			}
		}
		elementos = new Elemento[temp.size()];
		nodos = new ArrayList<Nodo>();
		for(int e=0;e<temp.size();e++)
			nodos.add(new Nodo(temp.get(e)));
	}
	
	public void buildTree(){
		while(nodos.size()>1){
					
			int n1 = 0;
			for(int n2 = 1;n2<nodos.size();n2++){
				if(nodos.get(n2).getVal().getFreq()<nodos.get(n1).getVal().getFreq())
					n1 = n2;
			}
			
			Nodo nd1 = nodos.remove(n1);
			
			n1 = 0;
			for(int n2 = 1;n2<nodos.size();n2++){
				if(nodos.get(n2).getVal().getFreq()<nodos.get(n1).getVal().getFreq())
					n1 = n2;
			}
			
			Nodo nd2 = nodos.remove(n1);
			
			
			if(nd1.getVal().getFreq()>nd2.getVal().getFreq()){
				Nodo nd = nd2;
				nd2 = nd1;
				nd1 = nd;
			}
			nd1.setCodigo("0");
			nd2.setCodigo("1");
			Elemento e = new Elemento(nd1.getVal().getNombre()+nd2.getVal().getNombre(), nd1.getVal().getFreq()+nd2.getVal().getFreq());
			Nodo nd = new Nodo(e, nd1, nd2);
			nodos.add(nd);
		}
	}
	
	public Elemento[] getElementos(){
		ArrayList<Elemento> al = nodos.get(0).getLeafs();
		for(int n=0;n<al.size();n++)
			elementos[n]=al.get(n);
		return elementos;
	}
	
	public String decode(String s){
		String msg = "";
		
		char[] bits = s.toCharArray();
		Nodo nd3 = nodos.get(0);
		int inicio = 0;
		int fin = 1;
		String uno = "1";
		String cero = "0";
		
		for(int z=0;z<s.length();z++){
			if(s.substring(inicio, fin).equals(cero)){
				if(nd3.hasLeft()==true){
					nd3 = nd3.getIzq();
					if(nd3.hasLeft()==false && nd3.hasRight()==false){
						msg = msg+nd3.getVal().getNombre();
						nd3 = nodos.get(0);
					}
				}
			}
			else if(s.substring(inicio, fin).equals(uno)){
				if(nd3.hasRight()==true){
					nd3 = nd3.getDer();
					if(nd3.hasLeft()==false && nd3.hasRight()==false){
						msg = msg+nd3.getVal().getNombre();
						nd3 = nodos.get(0);
					}
				}
			}
			else{
				nd3 = nodos.get(0);
				nd3 = nd3.getDer();
				nd3 = nd3.getIzq();
				msg = "Ingrese un caracter correcto por favor Gracias"+nd3.getVal().getNombre()+" "+s.substring(0, 1);
				break;
			}
			
			inicio++;
			fin++;
			
		}
		return msg;
	}
}
